package org.hw.algorithm.string;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @Program: demo
 * @Author: hewei
 * @Date: 2024-03-19 10:35
 * @Description:
 * 中缀表达式（我们常见的数学表达式）：3+4*5-6/3
 * 使用两个栈来模拟中缀表达式的运算
 **/
public class NifixExpression {
    /*数栈*/
    private static Stack<Integer> numStack = new Stack<>();
    /*符号栈*/
    private static Stack<String> operStack = new Stack<>();
    private static final String OPR_NAME="operator";
    private static final String NUM_NAME="number";
    /*表达式字符读取指针*/
    private static int index = 0;
    /*操作符和对应的优先级*/
    private static Map<String, Integer> operLevel = new HashMap<>() {{
        put("+", 0);
        put("-", 0);
        put("*", 1);
        put("/", 1);
    }};


    /**
     * 表达式计算
     * 一、循环遍历表达式，按规则压入栈
     *
     * 1、如果当前是数值，直接 入栈 到数栈
     * 2、如果当前是操作符：
     *  （1）、如果符号栈为空，直接 入栈 到符号栈
     *  （2）、如果 当前操作符的优先级 > 符号栈的栈顶操作符的优先级：直接 入栈 到符号栈
     *  （3）、如果 当前操作符的优先级 <= 符号栈的栈顶操作符的优先级：
     *      弹出数栈栈顶和次顶的两个元素，弹出符号栈栈顶操作符，三项进行运算，并将结果运算结果 压入数栈。然后再将当前操作符压入符号栈。
     *      例如 数栈顺序弹出 1 和 2，符号栈弹出 - ，那么结果为 2-1 =1，将结果 1 再压入数栈。
     *      最后一定记得将当前操作符压入 符号栈。
     *
     * 二、弹出栈中的元素，按规则进行计算
     *  1、弹出数栈的栈顶两个数，弹出符号栈栈顶的一个符号，三项进行运算，循环往复。
     *  2、直到符号栈为空，此时数栈中只有一个数，就是最终的结果，弹出即可。
     *
     * */
    public static Integer calculate(String expression) throws Exception {
        index=0;
        int len = expression.length();
        /*循环读取字符，并根据规则入栈操作数和操作符*/
        while (index < len) {
            Map<String, String> eleMap = getElement(expression);
            /*如果是数字直接入数栈*/
            if (eleMap.containsKey(NUM_NAME)) {
                String numstr=eleMap.get(NUM_NAME);
                numStack.push(Integer.parseInt(numstr));
            /*如果是操作符就按规则运算入栈*/
            }else{
                String oper=eleMap.get(OPR_NAME);
                /*如果 [操作符栈为空] 或者 [当前操作符优先级 > 操作符栈顶的元素的优先级]，则直接压入符号栈*/
                if (operStack.empty() || operLevel.get(oper) > operLevel.get(operStack.peek())) {
                    operStack.push(oper);
                /*如果 [当前符号优先级 <= 符号栈栈顶的符号优先级]，需要先计算栈顶符号与数栈栈顶两个元素，然后将计算结果压入数栈，再之后将当前操作符压入符号栈*/
                }else {
                    Integer num2 = numStack.pop();
                    Integer num1 = numStack.pop();
                    String o = operStack.pop();
                    Integer res = getResult(num1,num2,o);
                    numStack.push(res);
                    operStack.push(oper);
                }
            }
        }
        /*对符号栈和数栈进行出栈运算,次顶存放的是先运算的结果num1，栈顶是后运算的结果num2，所以运算时将num1在num2之前*/
        while (operStack.size() > 0) {
            Integer num2 = numStack.pop();
            Integer num1 = numStack.pop();
            String o = operStack.pop();
            numStack.push(getResult(num1,num2,o));
        }
        /*返回最终数栈中的运算结果*/
        return numStack.pop();
    }

    /**
     * 读取表达式中的多位数的数字字符串
     * 1、逐个读取数字字符进行连接，直到遇到操作符才停止
     * 2、每读取一位符号同时将 index 指针后移一位
     *
     * */
    private static Map<String,String> getElement(String expression) {
        /*如果当前是操作符则直接返回，并且 index 后移一位*/
        if (operLevel.containsKey(String.valueOf(expression.charAt(index)))) {
            return Map.of(OPR_NAME,String.valueOf(expression.charAt(index++)));
        }
        /*读取数字字符,每读取一位 index 后移一位*/
        StringBuilder sb = new StringBuilder();
        for (; index < expression.length(); index++) {
            String c = String.valueOf(expression.charAt(index));
            if (operLevel.containsKey(c)) {
                break;
            }
            sb.append(c);
        }
        return Map.of(NUM_NAME, sb.toString());
    }

    /**
     * 计算单步操作的结果
     * num1 前置操作数
     * num2 后置操作数
     * oper 操作符
     * */
    private static Integer getResult(Integer num1, Integer num2, String oper) throws Exception {
        switch (oper) {
            case "+":
                return num1 + num2;
            case "-":
                return num1 - num2;
            case "/":
                return num1 / num2;
            case "*":
                return num1 * num2;
            default:
                throw new Exception("无效操作符");
        }
    }

    public static void main(String[] args) {
//        String nifixExepress="5+2*5+4+100*2+1-100+30";
        String nifixExepress="3+4*5-6/3";
        try {
            System.out.println(NifixExpression.calculate(nifixExepress));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}